package com.mj.listen3.链表;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

/**
 * https://leetcode-cn.com/problems/merge-k-sorted-lists/
 */
public class _23_合并K个升序链表 {

    /**
     * 使用分治策略
     */
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;

        // 步长
        int step = 1;

        while (step < lists.length) {
            for (int i = 0; i + step < lists.length; i += (step << 1)) {
                lists[i] = mergeTwoLists(lists[i], lists[i + step]);
            }
            step = (step << 1);
        }


        return lists[0];
    }

    // 创建虚拟头节点
    ListNode head = new ListNode(0);

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;

        ListNode cur = head;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                cur.next = l1;
                cur = cur.next;
                l1 = l1.next;
            } else {
                cur.next = l2;
                cur = cur.next;
                l2 = l2.next;
            }
        }

        if (l1 == null) {
            // 把cur全部指向l2
            cur.next = l2;
        } else if (l2 == null) {
            // 把cur全部指向l1
            cur.next = l1;
        }

        return head.next;
    }


    /**
     * 使用小顶堆的性质
     *
     * @param lists
     * @return
     */
    public ListNode mergeKLists1(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;

        PriorityQueue<ListNode> priorityQueue = new PriorityQueue<>(
                new Comparator<ListNode>() {
                    @Override
                    public int compare(ListNode o1, ListNode o2) {
                        return o1.val - o2.val;
                    }
                }
        );

        for (ListNode listNode : lists) {
            if (listNode != null) {
                priorityQueue.offer(listNode);
            }
        }

        // 创建一个虚拟头节点
        ListNode head = new ListNode(0);
        // cur 指针用于链接后面堆中取出的节点
        ListNode cur = head;

        while (!priorityQueue.isEmpty()) {
            ListNode node = priorityQueue.poll();
            // 取出来连接到结果的链表上去
            cur.next = node;
            cur = cur.next;
            // 取出来的节点下一个节点不为空，就添加到小顶堆中去
            if (node.next != null) {
                priorityQueue.offer(node.next);
            }
        }

        return head.next;
    }

    public ListNode mergeKLists2(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;

        // 1、把数组链表每个几点都存储到新的数组中(集合)，进行排序
        List<ListNode> nodeList = new ArrayList<>();

        for (ListNode listNode : lists) {
            // 遍历到的都是链表(不是节点)
            while (listNode != null) {
                nodeList.add(listNode);
                listNode = listNode.next;
            }
        }

        // 2、排序
        nodeList.sort((o1, o2) -> o1.val - o2.val);

        // 3、依次取出节点，并合并成一个链表
        // 创建一个虚拟头节点
        ListNode head = new ListNode(0);
        ListNode cur = head;
        for (ListNode node : nodeList) {
            cur.next = node;
            cur = cur.next;
        }
        return head.next;
    }
}
